Decisions trees are used in a wide variety of software applications. For example, image processing programs, speech recognition programs, and search engines use decision trees to make probabilistic determinations of a class or characteristic of a data element. One type of decision tree, referred to as a binary decision tree, is formed in a branching tree structure, with an origin node branching to two child nodes, with some of the child nodes optionally functioning as parent nodes and branching in turn to two more child nodes, etc. Terminating nodes without child nodes are referred to as leaf nodes, while nodes that branch to child nodes are referred to as branch nodes.
The decision tree is traversed from top to bottom. Each branch node includes a classifier function, also referred to as a node descriptor, according to which the input data under analysis is evaluated to determine whether to branch right or left when proceeding down the tree structure. Thus, beginning at the origin, and proceeding until a leaf node is reached, at each branch node, the input data is evaluated by the classifier for the branch node, and traverses to the appropriate child node. Each leaf node represents a data class or characteristic, and also typically has assigned to it a probability of certainty that the input data is of the same class or characteristic as the leaf node. By traversing the decision tree from the origin node to a leaf node, a probabilistic determination of a class or characteristic of the input data can be made.
To date, evaluation of decision trees has been performed in software, which offers rapid prototyping and development times, flexible updating, etc. However, decision tree algorithms in software have been pushed to their limit by recent applications, such as in the computer gaming arts. For example, recently body part recognition software using decision tree analysis has been developed which can, in real time, evaluate incoming depth images from a depth camera input of a game console, to identify body parts of a moving image of a user. The output of the decision tree is used to perform skeletal modeling of the user, such that the user can interact with the game console in a three dimensional interaction space without holding a handheld controller.
However, such real-time, high throughput software-based decision tree algorithms consume significant power, and thus generate significant heat. They also are operating near their limit in terms of keeping up with the incoming images, and thus face difficulties if challenged by developers with a higher pixel count per image or an increasingly complex decision tree. Further, access to memory not in cache can create bandwidth bottlenecks and access-wait-time slowdowns in these software based algorithms. Finally, processor time devoted to classifying decision trees cannot be devoted to other internal processes of the game controller. As a result, increasing the speed while reducing the power consumption, heat, and cost of such real time software based decision tree evaluation of large data sets, remains a significant challenge.